package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-05 18:45
 **/
public class LeetCode1219 {

    static final int[][] DIRS = new int[][]{{1,0},{-1,0}, {0,1},{0,-1}};
    int[][] grid;
    int m;
    int n;
    int res;

    public int getMaximumGold(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    dfs(i, j, 0);
                }
            }
        }
        return res;
    }

    void dfs(int i, int j, int value) {
        value += grid[i][j];
        res = Math.max(res, value);

        int rec = grid[i][j];
        grid[i][j] = 0;
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                dfs(x, y, value);
            }
        }
        grid[i][j] = rec;
    }

}
